package dp;

public class _20_89_打家劫舍 {
    public int rob(int[] nums) {
    	if(nums.length == 2) {
    		return Math.max(nums[0], nums[1]);
    	}
    	if(nums.length == 1) {
    		return nums[0];
    	}
    	if(nums.length == 0) {
    		return 0;
    	}
    	int dp[] = new int[nums.length];
    	dp[0] = nums[0];
    	// dp[1]可能选1或0，这里选最大值
    	dp[1] = Math.max(nums[0], nums[1]);
    	for(int i = 2 ; i < nums.length; i++) {
    		// dp[i-2] + nums[i] 偷当前i，则加上前第二个的值
    		// dp[i-1] 不偷当前i，则取前一个值
    		dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
    	}
    	return dp[nums.length-1];
    }
    
    public static void main(String[] args) {
    	int nums[] = {};
		System.out.println(new _20_89_打家劫舍().rob(nums));
	}
}
